package com.example.result.alogrithm

import java.util.*
import java.util.concurrent.LinkedBlockingQueue
import kotlin.collections.ArrayList
import kotlin.collections.HashMap

class Graph(val v: Int, val edges: HashMap<Int, ArrayList<Int>> = HashMap()) {
    fun addEdge(f: Int, t: Int) {
        adj(f).apply {
            if (!contains(t)) {
                add(t)
            }
        }
    }

    fun adj(v: Int): ArrayList<Int> {
        if (edges[v] == null) {
            edges[v] = ArrayList<Int>()
        }
        return edges[v]!!
    }

    fun v() = v

}

abstract class Search(g: Graph, s: Int) {
    abstract fun marked(v: Int): Boolean
    abstract fun count(): Int
}

class DepthFirstSearch(g: Graph, s: Int) : Search(g, s) {
    lateinit var marked: Array<Boolean>
    var count = 0

    init {
        marked = Array<Boolean>(g.v()) { false }
        dfs(g, s)
    }


    override fun marked(v: Int): Boolean {
        return marked[v]

    }

    fun dfs(g: Graph, v: Int) {
        marked[v] = true
        count++
        g.adj(v).forEach {
            if (!marked(it)) {
                dfs(g, it)
            }
        }
    }

    override fun count(): Int {
        return count
    }

}

class DepthFirstPaths(g: Graph, s: Int) {
    private var s: Int = 0
    var marked: Array<Boolean>
    var edgeTo: Array<Int>

    init {
        this.s = s
        marked = Array(g.v()) { false }
        edgeTo = Array(g.v()) { 0 }
        dfs(g, s)
    }

    private fun dfs(g: Graph, v: Int) {
        marked[v] = true
        g.adj(v).forEach {
            if (!marked[it]) {
                edgeTo[it] = v
                dfs(g, it)
            }
        }
    }

    fun hasPathTo(v: Int): Boolean {
        return marked[v]
    }

    fun path(v: Int): Stack<Int>? {
        if (!hasPathTo(v)) {
            return null
        }
        var path = Stack<Int>()
        var x = v
        while (x != s) {
            path.push(x)
            x = edgeTo[x]
        }
        path.push(s)
        return path
    }
}

class BreadthFirstPaths(g: Graph, s: Int) {
    var s = 0
    lateinit var marked: Array<Boolean>
    lateinit var edgeTo: Array<Int>

    init {
        this.s = s
        marked = Array(g.v()) { false }
        edgeTo = Array(g.v()) { 0 }
        bfp(g, s)
    }

    private fun bfp(g: Graph, v: Int) {
        var queue = LinkedBlockingQueue<Int>()
        queue.add(v)
        var x = v;
        while (queue.isNotEmpty()) {
            x = queue.remove()
            marked[x] = true
            g.adj(x).forEach {
                if (!marked[it]) {
                    edgeTo[it] = x
                    queue.add(it)
                }
            }
        }
    }

    fun hasPathTo(v: Int): Boolean {
        return marked[v]
    }

    fun path(v: Int): Stack<Int>? {
        if (!hasPathTo(v)) {
            return null
        }
        var stack = Stack<Int>()
        var x = v
        while (x != s) {
            stack.push(x)
            x = edgeTo[x]
        }
        stack.push(x)
        return stack
    }
}
